/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/4 21:23
 */
// 反转字符串中的字符串
    // 不用辅助函数  去除额外空格+反转字符串+反转单个单词
    // https://leetcode.cn/problems/reverse-words-in-a-string/
public class Solution151 {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpaces(s);
        reverseString(sb, 0 , sb.length() - 1);
        reverseEachWords(sb);
        return sb.toString();
    }

    private void reverseEachWords(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' '){
                end++;
            }
            // 这里边界处理
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }

    private void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, sb.charAt(temp));
            start++;
            end--;
        }
    }

    private StringBuilder removeSpaces(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }
}
